Abstraction: There is a graph, with nodes and edges. Abstraction involves focusing on what is important and ignoring the rest - for example, we have not shown how much each tourist attraction cost for entry.
Generalization: Both problems are similar problems - ask students in what respect. Both problems involved going from one point to all other points and coming back to the original problem.
Algorithm: The method to solve the problem. How did you go about traversing the graph? For this kind of the problem, depth first is an intuitive route - you go down a path as far as you can and you backtrack if its the wrong path and try another one.
Pattern Matching: It seems that we can solve any "route finding" problem by drawing a graph for that - this is pattern matching.
Patterns we have looked at so far
Binary Search
Sorting
Induction/ Recursion
Today we will look at another pattern - pigeon hole principle
Review of Pigeonhole Principle
Explain basic Pigeonhole principle: If we put N+1 or more pigeons into N pigeon holes, then some pigeon hole must contain two or more pigeons.
Bag with beads of two colors and three draws; People seated around a dinner table with wrong dishes; Twelve numbers and choosing two whose difference is divisible by 11.
(Hav 2007) Seven points are placed inside a regular hexagon of side length 1. Show that at least two points are at most 1 unit apart
Partition the hexagon into 6 equal triangles. The diameter of each triangle (maximum distance between any two points within the triangle) is 1. At least one triangle must contain two points, hence proved.
(Hav 2007) 101 points are placed inside a 1x1 square. Show that some three points must form a triangle of area not more than 0.01
Divide the square into 50 vertical strips of 0.02 width each. Some strip must have 3 or more points. The maximum area of the triangle in any strip is 0.01
Show that in any group of five people, there are two who have an identical number of friends within the group
Hint: What is the pigeon and what is the pigeon hole?
Hint 2: Find two pigeon holes which cant be occupied simultaneously
Generalized pigeon hole: If there are Nk+1 pigeons and N pigeon holes, then at least one pigeon hole must contain at least k+1 items.
There are M football teams with 11 players each. They are gathered at an airport to go for a game. There are 10 flights with room for exactly M players, and one player will take his own helicopter to the game. What is the minimum and maximum number of full teams that can reach the game?
1 and (10M+1)/11 quotient - For minimum, what is the pigeon and what is the pigeon hole?
What is the largest number of squares on an 8x8 chessboard which can be colored green, so that any tromino (three squares in L shape) has at least one non-green square?
Answer: 32 (divide into 16 2x2 squares - if any square has more than 2 green, then it will have a green tromino) - what is the pigeon and what is the pigeon hole?
In the problem above, what is the smallest number of squares that can be colored green, so that every tromino has at least one green square?
Answer: 32 again! (in above 2x2 squares, with anything less than 32 greens, there will be a square with 0 or 1 green, hence a non-green tromino)
Homework:
MartinShCol - 1.15 - In a line up of 10 soldiers, what is the least number of soldiers that can be picked in order of either ascending or descending heights? Assume that no two soldiers have the same height.
Answer: Mark every person by two numbers - the max number of consecutive ascending chain he is part of, and max descending chain he is part of. No two people can have same (asc,des) pair (WHY?), hence with 10 people, someone must have a "4" in at least one of ascending or descending tag.
References:
Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg